package com.wtgroup.demo.leetcode.q122_买卖股票的最佳时机II;

/**
 * @author 60906
 * @date 2021/5/7 23:15
 */
public class Q122_Test {


    /**
     * <pre>
     *                 d
     *            c
     *       b
     *  a         c'
     * </pre>
     * <p>
     * 第三个是 c , 则是 a 买, d 卖;
     * c' , 则 a 买 b 卖, c' 买 d 卖.
     * "事后诸葛亮"思想, 找卖点, 买点选之前最低点.
     * 一次买卖后, 最低点重新算.
     *
     * 找卖点:
     * 当前价必上次价格高, 就尝试卖出, 可以理解为, 价格上升带来的"浮盈".
     * 当前不高于上次价, 说明上次如果真卖出, 是合理的. 于是, "锁定收益", 即将上次收益加到总利润中去.
     * 重新开启下一轮买卖. 最低价更新为当前价.
     *
     */
    private class Solution_My {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if (n < 2) {
                return 0;
            }

            int totalProfit = 0;
            int lastProfit = 0;
            int minPrice = prices[0];
            for (int i = 1; i < n; i++) {
                int p = prices[i];
                if (p < prices[i - 1]) {
                    // 上次的卖点定了, 如果有的话, 锁定上一轮的利润, 开启下一轮买卖.
                    // 锁定利润
                    totalProfit += lastProfit;
                    lastProfit = 0;
                    // 低价重新计算
                    minPrice = p;
                } else {
                    // 假设我卖了
                    lastProfit = p - minPrice;
                }
            }
            // 最后一段的利润有可能来不及锁定
            totalProfit += lastProfit;

            return totalProfit;
        }
    }

    /**
     * 极其简单的思路:
     * 当前价比上次价高, 就卖, 买价是上次价.
     * 当前价不高于上次价, 将其作为下次的买入价.
     * 注: [1,2,3,4] , 按照这个思路, 这个逻辑下, 买卖组合会是 (1,2), (2,3), (3,4),
     * 看起来不满足题意, 但没有关系, 最后答案和 (1,4) 一样!
     *
     * 实际就是LC的贪心方式. "贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。".
     */
    private class Solution_MyGreed {
        public int maxProfit(int[] prices) {
            // 一直就是"上一次价格"
            int buyPrice = Integer.MAX_VALUE;
            int profit = 0;
            for (int p : prices) {
                if (p > buyPrice) {
                    profit += p - buyPrice;
                }
                buyPrice = p;
            }
            return profit;
        }
    }

    // TODO 理解动态规划方式, 真正交易过程.
    /**
     * 动态规划 LC
     * 很难想到
     * 第 i 天只依赖 i-1 天状态. 状态随着遍历, 转移, 从而只需要依赖前一个就可以了.
     * 假设 0 表示手里没有股票, 1 表示有.
     * (i-1,i)
     * (0,0) => 今天没有任何操作.
     * (0,1) => 今天买入了.
     * (1,0) => 今天卖出了.
     * (1,1) => 今天没有操作.
     */
    private class Solution_Dp {
        public int maxProfit(int[] prices) {
            // 由于状态往后转移, 只需要保留上一次就可以了, 故, 备忘录只需要两个变量即可.
            int dp0 = 0; // 第 0 天, 没有股票最大利润是 0 ; 有股票, 最大利润是负的当天价格.
            int dp1 = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                dp0 = Math.max(dp0, dp1 + prices[i]);
                dp1 = Math.max(dp1, dp0 - prices[i]);
            }
            // 最后, 手里没有股票必是利润更大
            return dp0;
        }
    }

}
